題目連結: Palindrome Number

題目描述為給定一個帶有正負號的整數，問是否反轉後與原本的數相等。
題目的補充說明希望我們嘗試轉成字串處理以外的方法。

思路1： 取出所有位數

我們可以用一個陣列把每個位數的值存起來，按照題目要求一邊從頭另一邊從尾，往中間靠近，比較值是否相等。
如果原本的值 x 為負數則反轉後必不相等，只需要處理 x 非負的情形即可。

• 複雜度評估
  如果輸入的數字 x 為 n 位數，則需要轉換 n 次，比較是否相等為 n/2次，因為題目敘述中 x 為整數，並沒有限制 x 的大小，時間複雜度為 O(n)。此方法有另外宣告[]int 來存放轉換的數字，空間複雜度為 O(n)。

參考程式碼

func isPalindrome(x int) bool {  
    if x<0{
        return false
    }
    
    if x==0{
        return true
    }
    
    var nums []int
    var r int
    
    for x>0{
        r=x%10
        nums=append(nums,r)
        x=x/10
    }
    
    head:=0
    tail:=len(nums)-1

    
    for head<tail{
        if nums[head]!=nums[tail]{
            return false
        }
        head++
        tail--
    }
    return true
} 

思路2：比較反轉數

當輸入的數字 x>0 時，我們可以用 Day03-Reverse Integer 中提過的方法來求其反轉數 y ，然後比較是否相等。

• 複雜度評估
  如果輸入的數字 x 為 n 位數，則要重複此步驟 n 次。題目敘述中 x 為整數，並沒有限制 x 的大小，時間複雜度為 O(n)。此方法只用了常數個變數，空間複雜度為 O(1)。

參考程式碼

func isPalindrome(x int) bool {  
    if x<0{
        return false
    }
    
    if x==0{
        return true
    }
    
    ori:=x 
    rev:=0
    r:=0
   
    
    for x>0{
        r=x%10
        rev=rev*10+r
        x/=10
        
    }
    
    
    if ori==rev{
        return true
    }
    
    return false
}    

小結

此題與 Day03-Reverse Integer 題目思路類似，但此題並沒有限制輸入數字 x 的範圍。另外解法 2 的方法還可以再改進: 只需要保留 x 的前半部，以及反轉 x的後半部，然後比較是否相等即可。需要的步驟降為解法 2 的一半，設 x 為 n 位數，時間複雜度為 O(n)。此做法為網路上的分享解法。

我將分享解法轉換成 Go 語言版本作為解法 3 加上簡單的測試，上傳程式碼到此。